home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / smail-3.1.28 / pd / pathalias / arpatxt.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-03  |  13.1 KB  |  684 lines
  1. /* Smail SCCS ID: @(#)pd/pathalias/arpatxt.c    1.3 %G 00:43:18 */
  2. #ifndef lint
  3. static char *sccsid = "@(#)arpatxt.c    9.4 88/09/21";
  4. #endif
  5.  
  6. /*
  7.  * convert hosts.txt into pathalias format.
  8.  *
  9.  * alias rule: "host.dom.ain,nickname.arpa,..." -> host = nickname, ...
  10.  */
  11.  
  12. /* remove the next line for standard or research unix */
  13. #define BSD
  14.  
  15. #ifdef BSD
  16. #define strchr index
  17. #endif /* BSD */
  18.  
  19. #include <stdio.h>
  20. #include <ctype.h>
  21.  
  22. /* imports */
  23. extern char *re_comp(), *malloc(), *strchr(), *calloc();
  24. extern char *gets(), *strcpy(), *fgets();
  25. extern FILE *fopen();
  26.  
  27. typedef struct node node;
  28.  
  29. struct node {
  30.     node *child;    /* subdomain or member host */
  31.     node *parent;    /* parent domain */
  32.     node *next;    /* sibling in domain tree or host list */
  33.     char *name;    /* host name */
  34.     node *alias;    /* list of aliases */
  35.     node *bucket;
  36.     node *gateway;
  37.     int  flag;
  38. };
  39.  
  40. node *Top;
  41. int Atflag, Fflag, Iflag, Vflag;
  42. char *DotArpa = ".ARPA";
  43. char Fname[256], *Fstart;
  44.  
  45. node *newnode(), *find();
  46. char *strsave(), *lowercase();
  47. void crcinit();
  48. long fold();
  49. FILE *mkfile();
  50. int insert();
  51.  
  52. #define ISADOMAIN(n) ((n) && *((n)->name) == '.')
  53.  
  54. /* for node.flag */
  55. #define COLLISION 1
  56.  
  57. /* for formatprint() */
  58. #define PRIVATE        0
  59. #define HOSTS        1
  60. #define SUBDOMAINS    2
  61.  
  62. /* for usage() */
  63. #define USAGE "usage: %s [-i@] [-g gateway] [-p privatefile] [-f | -d directory] [file ...]\n"
  64.  
  65. main(argc, argv)
  66.     char **argv;
  67. {    int c;
  68.     char *progname;
  69.     extern char *optarg;
  70.     extern int optind;
  71.  
  72.     if ((progname = strchr(argv[0], '/')) != 0)
  73.         progname++;
  74.     else
  75.         progname = argv[0];
  76.     crcinit();
  77.  
  78.     Top = newnode();    /* needed for adding gateways */
  79.     while ((c = getopt(argc, argv, "d:fg:ip:v@")) != EOF)
  80.         switch(c) {
  81.         case 'd':
  82.             strcpy(Fname, optarg);
  83.             break;
  84.         case 'f':    /* filter mode -- write on stdout */
  85.             Fflag++;
  86.             break;
  87.         case 'g':
  88.             gateway(optarg);
  89.             break;
  90.         case 'i':
  91.             Iflag++;
  92.             break;
  93.         case 'p':
  94.             readprivates(optarg);
  95.             break;
  96.         case 'v':
  97.             Vflag++;
  98.             break;
  99.         case '@':
  100.             Atflag++;
  101.             break;
  102.         default:
  103.             usage(progname);
  104.         }
  105.  
  106.     if (Fflag && *Fname)
  107.         usage(progname);
  108.     if (Iflag)
  109.         (void) lowercase(DotArpa);
  110.     if (Top->gateway == 0)
  111.         fprintf(stderr, "%s: warning: no gateway to top level domains\n", progname);
  112.  
  113.     Fstart = Fname + strlen(Fname);
  114.     if (Fstart != Fname) {
  115.         *Fstart++ = '/';
  116.         *Fstart = 0;
  117.     }
  118.     /* should do the mkdir here instead of the shell script ...*/
  119.         
  120.     Top->name = "internet";
  121.     if (optind == argc)
  122.         scan();
  123.     else for ( ; optind < argc; optind++) {
  124.         if (freopen(argv[optind], "r", stdin) == 0) {
  125.             perror(argv[optind]);
  126.             continue;
  127.         }
  128.         scan();
  129.     }
  130.     setuniqflag(Top);    /* look for and mark collisions */
  131.     hashanalyze();        /* check hash algorithm performance */
  132.     merge();        /* make unique domain names */
  133.     dump(Top);        /* print */
  134.     return 0;
  135. }
  136.  
  137. scan()
  138. {    static first;
  139.     char buf0[BUFSIZ], buf1[BUFSIZ], buf2[BUFSIZ];
  140.  
  141.     if (first++ == 0)
  142.         (void) re_comp("^HOST.*SMTP");
  143.     while (gets(buf0) != 0) {
  144.         if (re_exec(buf0) == 0)
  145.             continue;
  146.         if (sscanf(buf0, "HOST : %[^:] : %[^: ]", buf1, buf2) != 2)
  147.             continue;
  148.         if (Iflag)
  149.             (void) lowercase(buf2);
  150.         if (insert(buf2) != 0)
  151.             fprintf(stderr, "input error: %s\n", buf0);
  152.     }
  153. }
  154. /*
  155.  * format of private file:
  156.  *    one per line, optionally followed by white space and comments
  157.  *    line starting with # is comment
  158.  */
  159. readprivates(pfile)
  160.     char *pfile;
  161. {    FILE *f;
  162.     node *n;
  163.     char buf[BUFSIZ], *bptr;
  164.  
  165.     if ((f = fopen(pfile, "r")) == 0) {
  166.         perror(pfile);
  167.         return;
  168.     }
  169.     while (fgets(buf, BUFSIZ, f) != 0) {
  170.         if (*buf == '#')
  171.             continue;
  172.         if ((bptr = strchr(buf, ' ')) != 0)
  173.             *bptr = 0;
  174.         if ((bptr = strchr(buf, '\t')) != 0)
  175.             *bptr = 0;
  176.         if (*buf == 0)
  177.             continue;
  178.         n = newnode();
  179.         n->name = strsave(buf);
  180.         hash(n);
  181.     }
  182.     (void) fclose(f);
  183. }
  184. usage(progname)
  185.     char *progname;
  186. {
  187.     fprintf(stderr, USAGE, progname);
  188.     exit(1);
  189. }
  190.  
  191. dumpgateways(ndom, f)
  192.     node *ndom;
  193.     FILE *f;
  194. {    node *n;
  195.  
  196.     for (n = ndom->gateway; n; n = n->next) {
  197.         fprintf(f, "%s ", n->name);
  198.         if (Atflag)
  199.             putc('@', f);
  200.         fprintf(f, "%s(%s)\t# gateway\n", ndom->name,
  201.                 ndom == Top ? "DEDICATED" : "LOCAL");
  202.     }
  203. }
  204.  
  205. gateway(buf)
  206.     char *buf;
  207. {    node *n, *dom;
  208.     char *dot;
  209.  
  210.     dot = strchr(buf, '.');
  211.     if (dot) {
  212.         dom = find(dot);
  213.         *dot = 0;
  214.     } else
  215.         dom = Top;
  216.  
  217.     n = newnode();
  218.     n->name = strsave(buf);
  219.     n->next = dom->gateway;
  220.     dom->gateway = n;
  221. }
  222.     
  223. int
  224. insert(buf)
  225.     char *buf;
  226. {    char host[BUFSIZ], *hptr, *dot;
  227.     node *n;
  228.  
  229.     for (hptr = host; *hptr = *buf++; hptr++)
  230.         if (*hptr == ',')
  231.             break;
  232.  
  233.     if (*hptr == ',')
  234.         *hptr = 0;
  235.     else
  236.         buf = 0;    /* no aliases */
  237.  
  238.     if ((dot = strchr(host, '.')) == 0)
  239.         return 1;    /* can't happen */
  240.     
  241.     if (strcmp(dot, DotArpa) == 0)
  242.         buf = 0;        /* no aliases */
  243.  
  244.     n = find(dot);
  245.     *dot = 0;
  246.  
  247.     addchild(n, host, buf);
  248.     return 0;
  249. }
  250.  
  251. node *
  252. find(domain)
  253.     char *domain;
  254. {    char *dot;
  255.     node *parent, *child;
  256.  
  257.     if (domain == 0)
  258.         return Top;
  259.     if ((dot = strchr(domain+1, '.')) != 0) {
  260.         parent = find(dot);
  261.         *dot = 0;
  262.     } else
  263.         parent = Top;
  264.  
  265.     for (child = parent->child; child; child = child->next)
  266.         if (strcmp(domain, child->name) == 0)
  267.             break;
  268.     if (child == 0) {
  269.         child = newnode();
  270.         child->next = parent->child;
  271.         parent->child = child;
  272.         child->parent = parent;
  273.         child->name = strsave(domain);
  274.     }
  275.     return child;
  276. }
  277.  
  278. node *
  279. newnode()
  280. {
  281.     node *n;
  282.  
  283.     if ((n = (node *) calloc(1, sizeof(node))) == 0)
  284.         abort();
  285.     return n;
  286. }
  287.  
  288. char *
  289. strsave(buf)
  290.     char *buf;
  291. {    char *mstr;
  292.  
  293.     if ((mstr = malloc(strlen(buf)+1)) == 0)
  294.         abort();
  295.     strcpy(mstr, buf);
  296.     return mstr;
  297. }
  298.  
  299. addchild(n, host, aliases)
  300.     node *n;
  301.     char *host, *aliases;
  302. {    node *child;
  303.  
  304.     /* check for dups?  nah! */
  305.     child = newnode();
  306.     child->name = strsave(host);
  307.     child->parent = n;
  308.     child->next = n->child;
  309.     makealiases(child, aliases);
  310.     n->child = child;
  311. }
  312.  
  313. /* yer basic tree walk to make output */
  314. dump(n)
  315.     node *n;
  316. {    node *child;
  317.     FILE *f;
  318.     int privates;
  319.  
  320.     /* sanity check */
  321.     if (n != Top && ! ISADOMAIN(n))
  322.         abort();
  323.  
  324.     f = mkfile(n);        /* prepare the output file */
  325.     privates = domprint(n, f);        /* print this domain */
  326.     dumpgateways(n, f);    /* print any gateways to this domain */
  327.     if (privates || n == Top)
  328.         fputs("private {}\n", f);    /* end scope of privates */
  329.     if (Fflag)
  330.         putc('\n', f);
  331.     else
  332.         (void) fclose(f);
  333.     for (child = n->child; child; child = child->next)
  334.         if (child->child)
  335.             dump(child);
  336. }
  337.  
  338. qcmp(a, b)
  339.     node **a, **b;
  340. {
  341.     return strcmp((*a)->name, (*b)->name);
  342. }
  343.  
  344. domprint(n, f)
  345.     node *n;
  346.     FILE *f;
  347. {    node *table[8191], *child, *alias;
  348.     char *cost = 0;
  349.     int nelem, i, privates = 0;
  350.  
  351.     /*
  352.      * dump private definitions.  
  353.      * sort hosts and aliases for pretty output.
  354.      */
  355.     if (n != Top) {
  356.         i = 0;
  357.         for (child = n->child; child; child = child->next) {
  358.             table[i++] = child;
  359.             for (alias = child->alias; alias; alias = alias->next)
  360.                 table[i++] = alias;
  361.         }
  362.  
  363.         qsort((char *) table, i, sizeof(table[0]), qcmp);
  364.         privates = formatprint(f, table, i, PRIVATE, "private", cost);
  365.     }
  366.  
  367.     /* dump domains and aliases, sorted for pretty output */
  368.     i = 0;
  369.     for (child = n->child; child; child = child->next)
  370.         table[i++] = child;
  371.     qsort((char *) table, i, sizeof(table[0]), qcmp);
  372.  
  373.     /* cost is DEDICATED for hosts in top-level domains, LOCAL o.w. */
  374.     if (n->parent == Top && strchr(n->name + 1, '.') == 0)
  375.         cost = "DEDICATED";
  376.     else
  377.         cost = "LOCAL";
  378.  
  379.     (void) formatprint(f, table, i, HOSTS, n->name, cost);
  380.     (void) formatprint(f, table, i, SUBDOMAINS, n->name, "0");
  381.  
  382.     /* dump aliases */
  383.     nelem = i;
  384.     for (i = 0; i < nelem; i++) {
  385.         if ((alias = table[i]->alias) == 0)
  386.             continue;
  387.         fprintf(f, "%s = %s", table[i]->name, alias->name);
  388.         for (alias = alias->next; alias; alias = alias->next)
  389.             fprintf(f, ", %s", alias->name);
  390.         putc('\n', f);
  391.     }
  392.     return privates;
  393. }
  394.  
  395. int
  396. formatprint(f, table, nelem, type, lhs, cost)
  397.     FILE *f;
  398.     node **table;
  399.     char *lhs, *cost;
  400. {    int i, didprint;
  401.     char buf[128], *bptr;
  402.  
  403.     sprintf(buf, "%s%s{" /*}*/, lhs, type == PRIVATE ? " " : " = ");
  404.     bptr = buf + strlen(buf);
  405.  
  406.     didprint = 0;
  407.     for (i = 0; i < nelem; i++) {
  408.         if (type == PRIVATE && ! (table[i]->flag & COLLISION))
  409.             continue;
  410.         else if (type == HOSTS && ISADOMAIN(table[i]) )
  411.             continue;
  412.         else if (type == SUBDOMAINS && ! ISADOMAIN(table[i]) )
  413.             continue;
  414.  
  415.         if ((bptr - buf) + strlen(table[i]->name) > 69) {
  416.             *bptr = 0;
  417.             fprintf(f, "%s\n ", buf);    /* continuation */
  418.             bptr = buf;
  419.         }
  420.         sprintf(bptr, "%s, ", table[i]->name);
  421.         bptr += strlen(bptr);
  422.         didprint++;
  423.     }
  424.     *bptr = 0;
  425.  
  426.     if (didprint) {
  427.         fprintf(f, /*{*/ "%s}", buf);
  428.         if (type != PRIVATE)
  429.             fprintf(f, "(%s)", cost);
  430.         putc('\n', f);
  431.     }
  432.     return didprint;
  433. }
  434.  
  435. FILE *                
  436. mkfile(n)
  437.     node *n;
  438. {    node *parent;
  439.     char *bptr;
  440.     FILE *f;
  441.  
  442.     /* build up the domain name in Fname[] */
  443.     bptr = Fstart;
  444.     if (n == Top)
  445.         strcpy(bptr, n->name);
  446.     else {
  447.         strcpy(bptr, n->name + 1);    /* skip leading dot */
  448.         bptr = bptr + strlen(bptr);
  449.         parent = n->parent;
  450.         while (ISADOMAIN(parent)) {
  451.             strcpy(bptr, parent->name);
  452.             bptr += strlen(bptr);
  453.             parent = parent->parent;
  454.         }
  455.         *bptr = 0;
  456.     }
  457.  
  458.     /* get a stream descriptor */
  459.     if (Fflag) {
  460.         printf("# %s\n", Fstart);
  461.         f = stdout;
  462.     } else {
  463. #ifndef BSD
  464.         Fstart[14] = 0;
  465. #endif
  466.         if ((f = fopen(Fname, "w")) == 0) {
  467.             perror(Fname);
  468.             exit(1);
  469.         }
  470.     }
  471.     if (n == Top)
  472.         fprintf(f, "private {%s}\ndead {%s}\n", Top->name, Top->name);
  473.     return f;
  474. }
  475.  
  476. /* map to lower case in place.  return parameter for convenience */
  477. char *
  478. lowercase(buf)
  479.     char *buf;
  480. {    char *str;
  481.  
  482.     for (str = buf ; *str; str++)
  483.         if (isupper(*str))
  484.             *str -= 'A' - 'a';
  485.     return buf;
  486. }
  487.  
  488. /* get the interesting aliases, attach to n->alias */
  489. makealiases(n, line)
  490.     node *n;
  491.     char *line;
  492. {    char *next, *dot;
  493.     node *a;
  494.  
  495.     if (line == 0 || *line == 0)
  496.         return;
  497.  
  498.     for ( ; line; line = next) {
  499.         next = strchr(line, ',');
  500.         if (next)
  501.             *next++ = 0;
  502.         if ((dot = strchr(line, '.')) == 0)
  503.             continue;
  504.         if (strcmp(dot, DotArpa) != 0)
  505.             continue;
  506.         *dot = 0;
  507.  
  508.         if (strcmp(n->name, line) == 0)
  509.             continue;
  510.  
  511.         a = newnode();
  512.         a->name = strsave(line);
  513.         a->next = n->alias;
  514.         n->alias = a;
  515.     }
  516. }
  517.  
  518. /* make unique domain names */
  519. merge()
  520. {    register node *n;
  521.  
  522.     for (n = Top->child; n; n = n->next)
  523.         make_children_unique(n);
  524. }
  525.  
  526. /*
  527.  * another recursive tree walk, this time to make unique domain
  528.  * components.
  529.  *
  530.  * for domains like cc.umich.edu and cc.berkeley.edu, it's inaccurate
  531.  * to describe cc as a member of umich.edu or berkeley.edu.  (i.e., the
  532.  * lousy scoping rules for privates don't permit a clean syntax.)  so.
  533.  *
  534.  * to prevent confusion, tack on to any such domain name its parent domain
  535.  * and promote it in the tree.  e.g., make cc.umich and cc.berkeley
  536.  * subdomains of edu.
  537.  */
  538.  
  539. make_children_unique(parent)
  540.     node *parent;
  541. {    node *prev, *child, *next;
  542.     char buf[BUFSIZ];
  543.  
  544.     prev = 0;
  545.     for (child = parent->child; child; child = next) {
  546.         next = child->next;
  547.  
  548.         /* skip hosts */
  549.         if (!ISADOMAIN(child)) {
  550.             prev = child;
  551.             continue;
  552.         }
  553.  
  554.         /*
  555.          * promote non-unique domain, or any domain with a
  556.          * gateway.  (the latter get promoted all the way to
  557.          * top-level.)
  558.          */
  559.         if ((child->flag & COLLISION) == 0 && child->gateway == 0) {
  560.             /*
  561.              * uninteresting domain.  make its children
  562.              * unique and bump prev.
  563.              */
  564.             make_children_unique(child);
  565.             prev = child;
  566.             continue;
  567.         }
  568.  
  569.         /*
  570.          * gateway or dup domain name found.  don't bump
  571.          * prev: this node is moving up the tree.
  572.          */
  573.  
  574.         /* qualify child domain name */
  575.         sprintf(buf, "%s%s", child->name, parent->name);
  576.         cfree(child->name);
  577.         child->name = strsave(buf);
  578.  
  579.         /* unlink child out of sibling chain */
  580.         if (prev)
  581.             prev->next = child->next;
  582.         else
  583.             parent->child = child->next;
  584.  
  585.         /* link child in as peer of parent */
  586.         child->next = parent->next;
  587.         parent->next = child;
  588.         child->parent = parent->parent;
  589.  
  590.         /*
  591.          * reset collision flag; may promote again on
  592.          * return to caller.
  593.          */
  594.         child->flag &= ~COLLISION;
  595.         hash(child);
  596.     }
  597. }
  598.  
  599. /* another recursive tree walk, this time to set the COLLISION bit. */
  600. setuniqflag(n)
  601.     node *n;
  602. {    node *child, *alias;
  603.  
  604.     /* mark this node in the hash table */
  605.     hash(n);
  606.     /* mark the aliases of this node */
  607.     for (alias = n->alias; alias; alias = alias->next)
  608.         hash(alias);
  609.     /* recursively mark this node's children */
  610.     for (child = n->child; child; child = child->next)
  611.         setuniqflag(child);
  612. }
  613.  
  614. #define NHASH 8191        /* must be prime */
  615. node *Htable[NHASH];        /* hash table */
  616.  
  617. hash(n)
  618.     node *n;
  619. {    node **bucket, *b;
  620.  
  621.     bucket = Htable + (fold(n->name) % NHASH);
  622.     for (b = *bucket; b; b = b->bucket)
  623.         if (strcmp(n->name, b->name) == 0) {
  624.             b->flag |= COLLISION;
  625.             n->flag |= COLLISION;
  626.             return;
  627.         }
  628.  
  629.     n->bucket = *bucket;
  630.     *bucket = n;
  631. }
  632.  
  633. /* stolen from pathalias:addnode.c, q.v. */
  634. #define POLY    0x48000000        /* 31-bit polynomial */
  635. long CrcTable[128];
  636.  
  637. void
  638. crcinit()
  639. {    register int i,j;
  640.     register long sum;
  641.  
  642.     for (i = 0; i < 128; i++) {
  643.         sum = 0;
  644.         for (j = 7-1; j >= 0; --j)
  645.             if (i & (1 << j))
  646.                 sum ^= POLY >> j;
  647.         CrcTable[i] = sum;
  648.     }
  649. }
  650.  
  651. long
  652. fold(s)
  653.     register char *s;
  654. {    register long sum = 0;
  655.     register int c;
  656.  
  657.     while (c = *s++)
  658.         sum = (sum >> 7) ^ CrcTable[(sum ^ c) & 0x7f];
  659.     return sum;
  660. }
  661.  
  662. hashanalyze()
  663. {    int nodecount = 0, maxlen = 0, len, i, probes = 0;
  664.     node *n;
  665.  
  666.     if (!Vflag)
  667.         return;
  668.  
  669.     for (i = 0; i < NHASH; i++) {
  670.         len = 0;
  671.         for (n = Htable[i]; n; n = n->bucket) {
  672.             len++;
  673.             probes += len;
  674.         }
  675.         nodecount += len;
  676.         if (len > maxlen)
  677.             maxlen = len;
  678.     }
  679.     fprintf(stderr,
  680.       "load = %2.2f, probes/access = %2.2f, %d nodes, max chain is %d\n",
  681.       (double) nodecount / (double) NHASH,
  682.       (double) probes / (double) nodecount, nodecount, maxlen);
  683. }
  684.